package com.soul.sort;

/**
 * 快速排序
 */
public class QuickSort {

    private final static int cutoff = 2;
    public static void sort(int[] a){
        qsort(a,0,a.length-1);
    }

    private static void qsort(int[] a,int l,int r){
        if (cutoff <= r - l){
            int pivot = getPivot(a,l,r);
            int i = l,j = r - 1;
            //将剩余所有元素与中间值比较，小的放左边，大的放右边
            while(true){
                while(a[++i] < pivot){}
                while(a[--j] > pivot){}
                if (i < j){
                    SortUtil.swap(a,i,j);
                }else break;
            }
            SortUtil.swap(a,i,r-1);
            qsort(a,l,i);//将左边再次执行
            qsort(a,i,r);//将右边再次执行
        }else {
            //达到一定阈值之后采用插入排序排好序列
            InsertionSort.sort(a,l,r-l+1);
        }
    }

    //每次将首个元素，与中间，最后元素进行排序
    private static int getPivot(int[] a,int l,int r){
        int c = (l + r) / 2;
        if (a[l] > a[c]){
            SortUtil.swap(a,l,c);
        }
        if (a[l] > a[r]){
            SortUtil.swap(a,l,r);
        }
        if (a[c] > a[r]){
            SortUtil.swap(a,c,r);
        }
        //将中间值存放到数组末尾的前一个位置
        SortUtil.swap(a,c,r-1);
        return a[r-1];
    }
}
